![]() ![]() ![]() |
The library provides four basic kinds of sorted associative containers: Set api, MultiSet api, Map api and MultiMap api and four basic kinds of hash tables: HashSet api, HashMultiSet api, HashMap api and HashMultiMap api.
All of the sorted associated containers are parameterized with an ordering
relation compare
that induces a total ordering on elements
of the containers.
In addition, Map
and MultiMap
associate an
arbitrary object with the key.
The object of type Predicate2
is called the
comparison object of a container.
All of the hash tables are parammeterized on a hash function
HashFunction api that maps element of the keyinto integers, and a
Predicate2
function that induces an equivalens relation
on the elements of the key.
In addition, HashMap
and HashMultiMap
associate an
arbitrary object with the key.
With sorted associated containers, when we talk about equality of keys we
mean the equivalence relation imposed by the comparison object.
That is, two keys k1
and k2
are considered to be
equal if for the comparison object comp
,
comp.compare(k1, k2) == false && comp.compare(k2, k1) == false
.
With hash tables, when we talk about equality of keys we mean equivalens
relation imposed by the key-equivalens object and not the ==
operation.
That is, two keys k1
and k2
are considered to be
equal if for the key-equivalens object comp
,
comp.compare(k1, k2) == true
.
An associative container (either sorted or hashed) supports unique keys
if it may contain at most one element for each key.
Otherwise, it supports equal keys.
Set
, Map
, HashSet
and
HashMap
support unique keys.
MultiSet
, MultiMap
, HashMultiSet
and
HashMultiMap
support equal keys.
For Set
, MultiSet
, HashSet
and
HashMultiSet
the value object is the same as the key object.
For Map
, MultiMap
, HashMap
and
HashMultiMap
it is equal to
Pair(Object key, Object value)
.
Iterators of a sorted associative container is of the bidirectional iterator
category, while that of hash tables is of the forward iterator category.
insert
does not affect the validity of iterators and
references to the container, and erase
invalidates only the
iterators and references to the erased elements.
In the following table, X
is an associative container class,
a
is an instance of X
, a_uniq
is an
instance of X
when X
supports unique keys,
and a_eq
is an instance of X
when X
supports multiple keys, i
and j
satisfy input
iterator requirements, [i,j)
is a valid range, p
is a valid iterator to a
, q
is a dereferenceable
iterator to a
, [q1,q2)
is a valid range in
a
, t
is a value object and k
is a key object.
The associative requirements are defined in the AssociativeContainer api interface.
expression | return type | assertion/note pre/post-condition | complexity | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a_uniq.insert(t)
|
pair(Iterator,Boolean)
|
inserts t if and only if there is no element in the container
with key equal to the key of t . The Boolean
component of the returned pair indicates whether the insertion takes
place and the Iterator component of the pair points to the
element with key equal to the key of t .
| expected logarithmic | ||||||||||||||||||||
a_eq.insert(t)
|
Iterator
|
inserts t and returns the iterator pointing to the newly
inserted element.
| expected logarithmic | ||||||||||||||||||||
a.insert(i, j)
|
void
|
inserts the elements from the range [i,j) into the container.
|
Expected Nlog(size()+N) (N is the distance from
i to j ) in general; expected linear if
[i,j) is sorted according to c
| ||||||||||||||||||||
a.erase(k)
|
int
|
erases all the elements in the container with key equal to
k .returns the number of erased elements. |
expected log(size()) + count(k)
|
The table entrie in the complexity column are in some cases qualified by the
word expected, meaning that the expected (or average) time in
required to satisfy the indicated bound, rather than the worst-case time.
For example expected logarithmic means that the expected time must be
O(log size())
, which is as looser requirement than requiring
the worst-case time to be logarithmic.
Note that an expected time requirement is also met by an implementation for
which the amortized meets the bound; i.e., the stated expected time
requirements allow implementations with either expected or amortized time
bounds.
![]() ![]() ![]() |